import { get } from 'http'

class DoublyLinkedList {
    constructor () {
        this.head = null
        this.tail = null
        this.length = 0
    }

    append (data) {
        const newNode = new LinkedListNode(data)
        if (this.length) {
            newNode.prev = this.tail
            this.tail.next = newNode
            this.tail = newNode
        } else {
            this.head = newNode
            this.tail = newNode
        }
        this.length += 1
    }

    insert (position, data) {
        // 越界判断：1、非负数，2：不得大于链表元素长度
        if (position < 0 || position > this.length) return false
        const newNode = new LinkedListNode(data)

        if (this.length == 0) {
            this.head = newNode
            this.tail = newNode
        } else {
            if (position == 0) {
                newNode.next = this.head
                this.head.prev = newNode
                this.head = newNode
            } else if (position == this.length) {
                this.tail.next = newNode
                newNode.prev = this.tail
                this.tail = newNode
            } else {
                let current = this.head
                let i = 0
                let previous = null
                while (i++ < position) {
                    current = current.next
                }
                newNode.prev = current.prev
                newNode.next = current
                current.prev.next = newNode
                current.prev = newNode
            }
        }

        this.length += 1
        return true
    }

    get (position) {
        // 越界判断：1、非负数，2：不得大于链表元素长度
        if (position < 0 || position >= this.length) return false

        // 优化思路
        // this.length / 2 > position: 从后往前遍历
        // this.length / 2 < position: 从前往后遍历
        let current = this.head
        let i = 0
        while (i++ < position) {
            current = current.next
        }
        return current.data
    }

    indexOf (data) {
        let index = 0
        let current = this.head
        while (current) {
            if (current.data == data) {
                return index
            }
            current = current.next
            index += 1
        }
        return -1
    }

    update (index, newData) {
        // 越界判断：1、非负数，2：不得大于链表元素长度
        if (index < 0 || index >= this.length) return false

        let i = 0
        let current = this.head
        while (i++ < index) {
            current = current.next
        }
        current.data = newData
        return true
    }

    removeAt (position) {
        // 越界判断：1、非负数，2：不得大于链表元素长度
        if (position < 0 || position >= this.length) return false
        let current = this.head

        if (this.length == 1) {
            this.head = null
            this.tail = null
        } else {
            if (position == 0) {
                this.head = current.next
                this.head.prev = null
            } else if (position == this.length - 1) {
                current = this.tail
                this.tail = this.tail.prev
                this.tail.next = null
            } else {
                let i = 0
                let previous = null
                while (i++ < position) {
                    current = current.next
                }
                current.prev.next = current.next
                current.next.prev = current.prev
            }
        }

        this.length--

        return current.data
    }

    remove (data) {
        let position = this.indexOf(data)
        return this.removeAt(position)
    }

    isEmpty () {
        return !this.length
    }

    size () {
        return this.length
    }

    toString () {
        return this.backwardString()
    }

    forwardString () {
        let current = this.tail
        let resultString = ''

        while (current) {
            resultString += current.data + ' '
            current = current.prev
        }
        return resultString
    }

    backwardString () {
        let current = this.head
        let resultString = ''

        while (current) {
            resultString += current.data + ' '
            current = current.next
        }
        return resultString
    }
}

class LinkedListNode {
    constructor (data) {
        this.data = data
        this.next = null
        this.prev = null
    }
}

export default DoublyLinkedList
